<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Pseudo-Random Numbers</title>
<meta name="description" content="Pseudo-Random Numbers">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00350_archivos/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">
 <h1><br clear="ALL"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">Pseudo-Random Numbers</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
Computers normally cannot generate really random numbers, but frequently
are used to generate sequences of pseudo-random numbers. These are generated
by some algorithm, but
appear for all practical purposes to be really random. Random numbers
are used in many applications, including simulation.
</p><p>
</p><p>
A common pseudo-random number generation technique is called the linear
congruential method. If the last pseudo-random number generated was <i>L</i>,
then the next number is generated
by evaluating ( <img alt="tex2html_wrap_inline32" src="acm-00350_archivos/350img1.gif" align="MIDDLE" height="27" width="143"> , where <i>Z</i> is a constant
multiplier, <i>I</i> is a constant increment, and <i>M</i> is a constant modulus.
For example, suppose <i>Z</i> is 7, <i>I</i> is 5, and <i>M</i> is 12. If the first
random number (usually called the <i>seed</i>) is 4, then we can determine the
next few pseudo-random numbers are follows:
</p><p>
</p><p> <img alt="tabular21" src="acm-00350_archivos/350img2.gif" align="BOTTOM" height="152" width="673"> </p><p>
</p><p>
As you can see, the sequence of pseudo-random numbers generated by this
technique repeats after six numbers. It should be clear that the longest
sequence that can be generated using
this technique is limited by the modulus, <i>M</i>.
</p><p>
</p><p>
In this problem you will be given sets of values for <i>Z</i>, <i>I</i>, <i>M</i>, and the
seed, <i>L</i>. Each of these will have no more than four digits. For each such
set of values you are to determine the length
of the cycle of pseudo-random numbers that will be generated. But be
careful: the cycle might not begin with the seed!
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Input</a></font></h2>
<p>
Each input line will contain four integer values, in order, for <i>Z</i>, <i>I</i>, <i>M</i>,
and <i>L</i>. The last line will contain four zeroes, and marks the end of the
input data. <i>L</i> will be less than <i>M</i>.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">Output</a></font></h2>
<p>
For each input line, display the case number (they are sequentially numbered,
starting with 1) and the length of the sequence of pseudo-random numbers
before the sequence is repeated.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">Sample Input</a></font></h2>
<p>
</p><pre>7 5 12 4
5173 3849 3279 1511
9111 5309 6000 1234
1079 2136 9999 1237
0 0 0 0</pre>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">Sample Output</a></font></h2>
<p>
</p><pre>Case 1: 6
Case 2: 546
Case 3: 500
Case 4: 220</pre>
<p>
</p></body></html>